Search Results

Documents authored by Sharir, Micha

Document
DOI: 10.4230/LIPIcs.ESA.2023.67
The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs

Authors: Haim Kaplan, Matthew J. Katz, Rachel Saban, and Micha Sharir

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We study the reverse shortest path problem on disk graphs in the plane. In this problem we consider the proximity graph of a set of n disks in the plane of arbitrary radii: In this graph two disks are connected if the distance between them is at most some threshold parameter r. The case of intersection graphs is a special case with r = 0. We give an algorithm that, given a target length k, computes the smallest value of r for which there is a path of length at most k between some given pair of disks in the proximity graph. Our algorithm runs in O^*(n^{5/4}) randomized expected time, which improves to O^*(n^{6/5}) for unit disk graphs, where all the disks have the same radius. Our technique is robust and can be applied to many variants of the problem. One significant variant is the case of weighted proximity graphs, where edges are assigned real weights equal to the distance between the disks or between their centers, and k is replaced by a target weight w. In other variants, we want to optimize a parameter different from r, such as a scale factor of the radii of the disks. The main technique for the decision version of the problem (determining whether the graph with a given r has the desired property) is based on efficient implementations of BFS (for the unweighted case) and of Dijkstra’s algorithm (for the weighted case), using efficient data structures for maintaining the bichromatic closest pair for certain bicliques and several distance functions. The optimization problem is then solved by combining the resulting decision procedure with enhanced variants of the interval shrinking and bifurcation technique of [R. Ben Avraham et al., 2015].
Cite as

Haim Kaplan, Matthew J. Katz, Rachel Saban, and Micha Sharir. The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.ESA.2023.67,
  author =	{Kaplan, Haim and Katz, Matthew J. and Saban, Rachel and Sharir, Micha},
  title =	{{The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.67},
  URN =		{urn:nbn:de:0030-drops-187208},
  doi =		{10.4230/LIPIcs.ESA.2023.67},
  annote =	{Keywords: Computational geometry, geometric optimization, disk graphs, BFS, Dijkstra’s algorithm, reverse shortest path}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.22
Improved Algebraic Degeneracy Testing

Authors: Jean Cardinal and Micha Sharir

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
In the classical linear degeneracy testing problem, we are given n real numbers and a k-variate linear polynomial F, for some constant k, and have to determine whether there exist k numbers a_1,…,a_k from the set such that F(a_1,…,a_k) = 0. We consider a generalization of this problem in which F is an arbitrary constant-degree polynomial, we are given k sets of n real numbers, and have to determine whether there exists a k-tuple of numbers, one in each set, on which F vanishes. We give the first improvement over the naïve O^*(n^{k-1}) algorithm for this problem (where the O^*(⋅) notation omits subpolynomial factors). We show that the problem can be solved in time O^*(n^{k - 2 + 4/(k+2)}) for even k and in time O^*(n^{k - 2 + (4k-8)/(k²-5)}) for odd k in the real RAM model of computation. We also prove that for k = 4, the problem can be solved in time O^*(n^2.625) in the algebraic decision tree model, and for k = 5 it can be solved in time O^*(n^3.56) in the same model, both improving on the above uniform bounds. All our results rely on an algebraic generalization of the standard meet-in-the-middle algorithm for k-SUM, powered by recent algorithmic advances in the polynomial method for semi-algebraic range searching. In fact, our main technical result is much more broadly applicable, as it provides a general tool for detecting incidences and other interactions between points and algebraic surfaces in any dimension. In particular, it yields an efficient algorithm for a general, algebraic version of Hopcroft’s point-line incidence detection problem in any dimension.
Cite as

Jean Cardinal and Micha Sharir. Improved Algebraic Degeneracy Testing. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.SoCG.2023.22,
  author =	{Cardinal, Jean and Sharir, Micha},
  title =	{{Improved Algebraic Degeneracy Testing}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.22},
  URN =		{urn:nbn:de:0030-drops-178723},
  doi =		{10.4230/LIPIcs.SoCG.2023.22},
  annote =	{Keywords: Degeneracy testing, k-SUM problem, incidence bounds, Hocroft’s problem, polynomial method, algebraic decision trees}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.42
On Reverse Shortest Paths in Geometric Proximity Graphs

Authors: Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Let S be a set of n geometric objects of constant complexity (e.g., points, line segments, disks, ellipses) in ℝ², and let ϱ: S× S → ℝ_{≥ 0} be a distance function on S. For a parameter r ≥ 0, we define the proximity graph G(r) = (S,E) where E = {(e₁,e₂) ∈ S×S ∣ e₁≠e₂, ϱ(e₁,e₂) ≤ r}. Given S, s,t ∈ S, and an integer k ≥ 1, the reverse-shortest-path (RSP) problem asks for computing the smallest value r^* ≥ 0 such that G(r^*) contains a path from s to t of length at most k. In this paper we present a general randomized technique that solves the RSP problem efficiently for a large family of geometric objects and distance functions. Using standard, and sometimes more involved, semi-algebraic range-searching techniques, we first give an efficient algorithm for the decision problem, namely, given a value r ≥ 0, determine whether G(r) contains a path from s to t of length at most k. Next, we adapt our decision algorithm and combine it with a random-sampling method to compute r^*, by efficiently performing a binary search over an implicit set of O(n²) candidate values that contains r^*. We illustrate the versatility of our general technique by applying it to a variety of geometric proximity graphs. For example, we obtain (i) an O^*(n^{4/3}) expected-time randomized algorithm (where O^*(⋅) hides polylog(n) factors) for the case where S is a set of pairwise-disjoint line segments in ℝ² and ϱ(e₁,e₂) = min_{x ∈ e₁, y ∈ e₂} ‖x-y‖ (where ‖⋅‖ is the Euclidean distance), and (ii) an O^*(n+m^{4/3}) expected-time randomized algorithm for the case where S is a set of m points lying on an x-monotone polygonal chain T with n vertices, and ϱ(p,q), for p,q ∈ S, is the smallest value h such that the points p' := p+(0,h) and q' := q+(0,h) are visible to each other, i.e., all points on the segment p'q' lie above or on the polygonal chain T.
Cite as

Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. On Reverse Shortest Paths in Geometric Proximity Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2022.42,
  author =	{Agarwal, Pankaj K. and Katz, Matthew J. and Sharir, Micha},
  title =	{{On Reverse Shortest Paths in Geometric Proximity Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.42},
  URN =		{urn:nbn:de:0030-drops-173277},
  doi =		{10.4230/LIPIcs.ISAAC.2022.42},
  annote =	{Keywords: Geometric optimization, proximity graphs, semi-algebraic range searching, reverse shortest path}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.51
Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection

Authors: Esther Ezra and Micha Sharir

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We develop data structures for intersection detection queries in four dimensions that involve segments, triangles and tetrahedra. Specifically, we study two main problems: (i) Preprocess a set of n tetrahedra in {ℝ}⁴ into a data structure for answering segment-intersection queries amid the given tetrahedra (referred to as segment-tetrahedron intersection queries), and (ii) Preprocess a set of n triangles in {ℝ}⁴ into a data structure that supports triangle-intersection queries amid the input triangles (referred to as triangle-triangle intersection queries). As far as we can tell, these problems have not been previously studied. For problem (i), we first present a "standard" solution which, for any prespecified value n ≤ s ≤ n⁶ of a so-called storage parameter s, yields a data structure with O^*(s) storage and expected preprocessing, which answers an intersection query in O^*(n/s^{1/6}) time (here and in what follows, the O^*(⋅) notation hides subpolynomial factors). For problem (ii), using similar arguments, we present a solution that has the same asymptotic performance bounds. We then improve the solution for problem (i), and present a more intricate data structure that uses O^*(n²) storage and expected preprocessing, and answers a segment-tetrahedron intersection query in O^*(n^{1/2}) time. Using the parametric search technique of Agarwal and Matoušek [P. K. Agarwal and J. Matoušek, 1993], we can obtain data structures with similar performance bounds for the ray-shooting problem amid tetrahedra in {ℝ}⁴. Unfortunately, so far we do not know how to obtain a similar improvement for problem (ii). Our algorithms are based on a primal-dual technique for range searching with semi-algebraic sets, based on recent advances in this area [P. K. Agarwal et al., 2021; J. Matoušek and Z. Patáková, 2015]. As this is a result of independent interest, we spell out the details of this technique. As an application, we present a solution to the problem of "continuous collision detection" amid moving tetrahedra in 3-space. That is, the workspace consists of n tetrahedra, each moving at its own fixed velocity, and the goal is to detect a collision between some pair of moving tetrahedra. Using our solutions to problems (i) and (ii), we obtain an algorithm that detects a collision in O^*(n^{12/7}) expected time. We also present further applications, including an output-sensitive algorithm for constructing the arrangement of n tetrahedra in ℝ⁴ and an output-sensitive algorithm for constructing the intersection or union of two or several nonconvex polyhedra in ℝ⁴.
Cite as

Esther Ezra and Micha Sharir. Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ezra_et_al:LIPIcs.ESA.2022.51,
  author =	{Ezra, Esther and Sharir, Micha},
  title =	{{Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.51},
  URN =		{urn:nbn:de:0030-drops-169895},
  doi =		{10.4230/LIPIcs.ESA.2022.51},
  annote =	{Keywords: Computational geometry, Ray shooting, Tetrahedra in \{\mathbb{R}\}⁴, Intersection queries in \{\mathbb{R}\}⁴, Polynomial partitioning, Range searching, Semi-algebraic sets, Tradeoff}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.4
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

Authors: Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Let 𝒯 be a set of n planar semi-algebraic regions in ℝ³ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess 𝒯 into a data structure so that for a query object γ, which is also a plate, we can quickly answer various intersection queries, such as detecting whether γ intersects any plate of 𝒯, reporting all the plates intersected by γ, or counting them. We focus on two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree algebraic arcs in ℝ³ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in ℝ³. These interesting special cases form the building blocks for the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we obtain a variety of results with different storage and query-time bounds, depending on the complexity of the input and query objects. For example, if 𝒯 is a set of plates and the query objects are arcs, we obtain a data structure that uses O^*(n^{4/3}) storage (where the O^*(⋅) notation hides subpolynomial factors) and answers an intersection query in O^*(n^{2/3}) time. Alternatively, by increasing the storage to O^*(n^{3/2}), the query time can be decreased to O^*(n^{ρ}), where ρ = (2t-3)/3(t-1) < 2/3 and t ≥ 3 is the number of parameters needed to represent the query arcs.
Cite as

Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2022.4,
  author =	{Agarwal, Pankaj K. and Aronov, Boris and Ezra, Esther and Katz, Matthew J. and Sharir, Micha},
  title =	{{Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.4},
  URN =		{urn:nbn:de:0030-drops-160126},
  doi =		{10.4230/LIPIcs.SoCG.2022.4},
  annote =	{Keywords: Intersection searching, Semi-algebraic range searching, Point-enclosure queries, Ray-shooting queries, Polynomial partitions, Cylindrical algebraic decomposition, Multi-level partition trees, Collision detection}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.57
Covering Points by Hyperplanes and Related Problems

Authors: Zuzana Patáková and Micha Sharir

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
For a set P of n points in ℝ^d, for any d ≥ 2, a hyperplane h is called k-rich with respect to P if it contains at least k points of P. Answering and generalizing a question asked by Peyman Afshani, we show that if the number of k-rich hyperplanes in ℝ^d, d ≥ 3, is at least Ω(n^d/k^α + n/k), with a sufficiently large constant of proportionality and with d ≤ α < 2d-1, then there exists a (d-2)-flat that contains Ω(k^{(2d-1-α)/(d-1)}) points of P. We also present upper bound constructions that give instances in which the above lower bound is tight. An extension of our analysis yields similar lower bounds for k-rich spheres.
Cite as

Zuzana Patáková and Micha Sharir. Covering Points by Hyperplanes and Related Problems. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 57:1-57:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{patakova_et_al:LIPIcs.SoCG.2022.57,
  author =	{Pat\'{a}kov\'{a}, Zuzana and Sharir, Micha},
  title =	{{Covering Points by Hyperplanes and Related Problems}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{57:1--57:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.57},
  URN =		{urn:nbn:de:0030-drops-160652},
  doi =		{10.4230/LIPIcs.SoCG.2022.57},
  annote =	{Keywords: Rich hyperplanes, Incidences, Covering points by hyperplanes}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.3
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model

Authors: Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We present subquadratic algorithms in the algebraic decision-tree model for several 3Sum-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ ∈ C, the number of intersection points between the segments of A and those of B that lie in Δ. The problems considered in this paper have been studied by Chan (2020), who gave algorithms that solve them, in the standard real-RAM model, in O((n²/log²n) log^O(1) log n) time. We present solutions in the algebraic decision-tree model whose cost is O(n^{60/31+ε}), for any ε > 0. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl (2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm.
Cite as

Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2021.3,
  author =	{Aronov, Boris and de Berg, Mark and Cardinal, Jean and Ezra, Esther and Iacono, John and Sharir, Micha},
  title =	{{Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.3},
  URN =		{urn:nbn:de:0030-drops-154363},
  doi =		{10.4230/LIPIcs.ISAAC.2021.3},
  annote =	{Keywords: Computational geometry, Algebraic decision-tree model, Polynomial partitioning, Primal-dual range searching, Order types, Point location, Hierarchical partitions}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.34
On Ray Shooting for Triangles in 3-Space and Related Problems

Authors: Esther Ezra and Micha Sharir

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We consider several problems that involve lines in three dimensions, and present improved algorithms for solving them. The problems include (i) ray shooting amid triangles in ℝ³, (ii) reporting intersections between query lines (segments, or rays) and input triangles, as well as approximately counting the number of such intersections, (iii) computing the intersection of two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections in a set of lines in ℝ³, and (v) output-sensitive construction of an arrangement of triangles in three dimensions. Our approach is based on the polynomial partitioning technique. For example, our ray-shooting algorithm processes a set of n triangles in ℝ³ into a data structure for answering ray shooting queries amid the given triangles, which uses O(n^{3/2+ε}) storage and preprocessing, and answers a query in O(n^{1/2+ε}) time, for any ε > 0. This is a significant improvement over known results, obtained more than 25 years ago, in which, with this amount of storage, the query time bound is roughly n^{5/8}. The algorithms for the other problems have similar performance bounds, with similar improvements over previous results. We also derive a nontrivial improved tradeoff between storage and query time. Using it, we obtain algorithms that answer m queries on n objects in max{O(m^{2/3}n^{5/6+{ε}} + n^{1+ε}), O(m^{5/6+ε}n^{2/3} + m^{1+ε})} time, for any ε > 0, again an improvement over the earlier bounds.
Cite as

Esther Ezra and Micha Sharir. On Ray Shooting for Triangles in 3-Space and Related Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ezra_et_al:LIPIcs.SoCG.2021.34,
  author =	{Ezra, Esther and Sharir, Micha},
  title =	{{On Ray Shooting for Triangles in 3-Space and Related Problems}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.34},
  URN =		{urn:nbn:de:0030-drops-138332},
  doi =		{10.4230/LIPIcs.SoCG.2021.34},
  annote =	{Keywords: Ray shooting, Three dimensions, Polynomial partitioning, Tradeoff}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.35
On Rich Lenses in Planar Arrangements of Circles and Related Problems

Authors: Esther Ezra, Orit E. Raz, Micha Sharir, and Joshua Zahl

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We show that the maximum number of pairwise non-overlapping k-rich lenses (lenses formed by at least k circles) in an arrangement of n circles in the plane is O(n^{3/2}log(n / k^3) k^{-5/2} + n/k), and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is O(n^{3/2}log(n/k^3) k^{-3/2} + n). Two independent proofs of these bounds are given, each interesting in its own right (so we believe). We then show that these bounds lead to the known bound of Agarwal et al. (JACM 2004) and Marcus and Tardos (JCTA 2006) on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.
Cite as

Esther Ezra, Orit E. Raz, Micha Sharir, and Joshua Zahl. On Rich Lenses in Planar Arrangements of Circles and Related Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ezra_et_al:LIPIcs.SoCG.2021.35,
  author =	{Ezra, Esther and Raz, Orit E. and Sharir, Micha and Zahl, Joshua},
  title =	{{On Rich Lenses in Planar Arrangements of Circles and Related Problems}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.35},
  URN =		{urn:nbn:de:0030-drops-138343},
  doi =		{10.4230/LIPIcs.SoCG.2021.35},
  annote =	{Keywords: Lenses, Circles, Polynomial partitioning, Incidences}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.41
Throwing a Sofa Through the Window

Authors: Dan Halperin, Micha Sharir, and Itay Yehuda

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We study several variants of the problem of moving a convex polytope K, with n edges, in three dimensions through a flat rectangular (and sometimes more general) window. Specifically: ii) We study variants where the motion is restricted to translations only, discuss situations where such a motion can be reduced to sliding (translation in a fixed direction), and present efficient algorithms for those variants, which run in time close to O(n^{8/3}). iii) We consider the case of a gate (an unbounded window with two parallel infinite edges), and show that K can pass through such a window, by any collision-free rigid motion, iff it can slide through it, an observation that leads to an efficient algorithm for this variant too. iv) We consider arbitrary compact convex windows, and show that if K can pass through such a window W (by any motion) then K can slide through a slab of width equal to the diameter of W. v) We show that if a purely translational motion for K through a rectangular window W exists, then K can also slide through W keeping the same orientation as in the translational motion. For a given fixed orientation of K we can determine in linear time whether K can translate (and hence slide) through W keeping the given orientation, and if so plan the motion, also in linear time. vi) We give an example of a polytope that cannot pass through a certain window by translations only, but can do so when rotations are allowed. vii) We study the case of a circular window W, and show that, for the regular tetrahedron K of edge length 1, there are two thresholds 1 > δ₁≈ 0.901388 > δ₂≈ 0.895611, such that (a) K can slide through W if the diameter d of W is ≥ 1, (b) K cannot slide through W but can pass through it by a purely translational motion when δ₁ ≤ d < 1, (c) K cannot pass through W by a purely translational motion but can do it when rotations are allowed when δ₂ ≤ d < δ₁, and (d) K cannot pass through W at all when d < δ₂. viii) Finally, we explore the general setup, where we want to plan a general motion (with all six degrees of freedom) for K through a rectangular window W, and present an efficient algorithm for this problem, with running time close to O(n⁴).
Cite as

Dan Halperin, Micha Sharir, and Itay Yehuda. Throwing a Sofa Through the Window. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{halperin_et_al:LIPIcs.SoCG.2021.41,
  author =	{Halperin, Dan and Sharir, Micha and Yehuda, Itay},
  title =	{{Throwing a Sofa Through the Window}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.41},
  URN =		{urn:nbn:de:0030-drops-138409},
  doi =		{10.4230/LIPIcs.SoCG.2021.41},
  annote =	{Keywords: Motion planning, Convex polytopes in 3D}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.56
On Rich Points and Incidences with Restricted Sets of Lines in 3-Space

Authors: Micha Sharir and Noam Solomon

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Let L be a set of n lines in ℝ³ that is contained, when represented as points in the four-dimensional Plücker space of lines in ℝ³, in an irreducible variety T of constant degree which is non-degenerate with respect to L (see below). We show: (1) If T is two-dimensional, the number of r-rich points (points incident to at least r lines of L) is O(n^{4/3+ε}/r²), for r ⩾ 3 and for any ε > 0, and, if at most n^{1/3} lines of L lie on any common regulus, there are at most O(n^{4/3+ε}) 2-rich points. For r larger than some sufficiently large constant, the number of r-rich points is also O(n/r). As an application, we deduce (with an ε-loss in the exponent) the bound obtained by Pach and de Zeeuw [J. Pach and F. de Zeeuw, 2017] on the number of distinct distances determined by n points on an irreducible algebraic curve of constant degree in the plane that is not a line nor a circle. (2) If T is two-dimensional, the number of incidences between L and a set of m points in ℝ³ is O(m+n). (3) If T is three-dimensional and nonlinear, the number of incidences between L and a set of m points in ℝ³ is O (m^{3/5}n^{3/5} + (m^{11/15}n^{2/5} + m^{1/3}n^{2/3})s^{1/3} + m + n), provided that no plane contains more than s of the points. When s = O(min{n^{3/5}/m^{2/5}, m^{1/2}}), the bound becomes O(m^{3/5}n^{3/5}+m+n). As an application, we prove that the number of incidences between m points and n lines in ℝ⁴ contained in a quadratic hypersurface (which does not contain a hyperplane) is O(m^{3/5}n^{3/5} + m + n). The proofs use, in addition to various tools from algebraic geometry, recent bounds on the number of incidences between points and algebraic curves in the plane.
Cite as

Micha Sharir and Noam Solomon. On Rich Points and Incidences with Restricted Sets of Lines in 3-Space. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sharir_et_al:LIPIcs.SoCG.2021.56,
  author =	{Sharir, Micha and Solomon, Noam},
  title =	{{On Rich Points and Incidences with Restricted Sets of Lines in 3-Space}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.56},
  URN =		{urn:nbn:de:0030-drops-138551},
  doi =		{10.4230/LIPIcs.SoCG.2021.56},
  annote =	{Keywords: Lines in space, Rich points, Polynomial partitioning, Incidences}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.8
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets

Authors: Boris Aronov, Esther Ezra, and Micha Sharir

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets A, B, and C of points in the plane, that satisfy a certain polynomial equation or two equations. The best known instance of such a problem is testing for the existence of a collinear triple of points in A×B×C, a classical 3SUM-hard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decision-tree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decision-tree model, that uses only roughly O(n^(28/15)) constant-degree polynomial sign tests, for the special case where two of the sets lie on one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to any other problem where we seek a triple that satisfies a single polynomial equation, e.g., determining whether A× B× C contains a triple spanning a unit-area triangle. This result extends recent work by Barba et al. [Luis Barba et al., 2019] and by Chan [Timothy M. Chan, 2020], where all three sets A, B, and C are assumed to be one-dimensional. While there are common features in the high-level approaches, here and in [Luis Barba et al., 2019], the actual analysis in this work becomes more involved and requires new methods and techniques, involving polynomial partitions and other related tools. As a second application of our technique, we again have three n-point sets A, B, and C in the plane, and we want to determine whether there exists a triple (a,b,c) ∈ A×B×C that simultaneously satisfies two real polynomial equations. For example, this is the setup when testing for the existence of pairs of similar triangles spanned by the input points, in various contexts discussed later in the paper. We show that problems of this kind can be solved with roughly O(n^(24/13)) constant-degree polynomial sign tests. These problems can be extended to higher dimensions in various ways, and we present subquadratic solutions to some of these extensions, in the algebraic decision-tree model.
Cite as

Boris Aronov, Esther Ezra, and Micha Sharir. Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.8,
  author =	{Aronov, Boris and Ezra, Esther and Sharir, Micha},
  title =	{{Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.8},
  URN =		{urn:nbn:de:0030-drops-121666},
  doi =		{10.4230/LIPIcs.SoCG.2020.8},
  annote =	{Keywords: Algebraic decision tree, Polynomial partition, Collinearity testing, 3SUM-hard problems, Polynomials vanishing on Cartesian products}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.52
How to Find a Point in the Convex Hull Privately

Authors: Haim Kaplan, Micha Sharir, and Uri Stemmer

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We study the question of how to compute a point in the convex hull of an input set S of n points in ℝ^d in a differentially private manner. This question, which is trivial without privacy requirements, turns out to be quite deep when imposing differential privacy. In particular, it is known that the input points must reside on a fixed finite subset G ⊆ ℝ^d, and furthermore, the size of S must grow with the size of G. Previous works [Amos Beimel et al., 2010; Amos Beimel et al., 2019; Amos Beimel et al., 2013; Mark Bun et al., 2018; Mark Bun et al., 2015; Haim Kaplan et al., 2019] focused on understanding how n needs to grow with |G|, and showed that n=O(d^2.5 ⋅ 8^(log^*|G|)) suffices (so n does not have to grow significantly with |G|). However, the available constructions exhibit running time at least |G|^d², where typically |G|=X^d for some (large) discretization parameter X, so the running time is in fact Ω(X^d³). In this paper we give a differentially private algorithm that runs in O(n^d) time, assuming that n=Ω(d⁴ log X). To get this result we study and exploit some structural properties of the Tukey levels (the regions D_{≥ k} consisting of points whose Tukey depth is at least k, for k=0,1,…). In particular, we derive lower bounds on their volumes for point sets S in general position, and develop a rather subtle mechanism for handling point sets S in degenerate position (where the deep Tukey regions have zero volume). A naive approach to the construction of the Tukey regions requires n^O(d²) time. To reduce the cost to O(n^d), we use an approximation scheme for estimating the volumes of the Tukey regions (within their affine spans in case of degeneracy), and for sampling a point from such a region, a scheme that is based on the volume estimation framework of Lovász and Vempala [László Lovász and Santosh S. Vempala, 2006] and of Cousins and Vempala [Ben Cousins and Santosh S. Vempala, 2018]. Making this framework differentially private raises a set of technical challenges that we address.
Cite as

Haim Kaplan, Micha Sharir, and Uri Stemmer. How to Find a Point in the Convex Hull Privately. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.SoCG.2020.52,
  author =	{Kaplan, Haim and Sharir, Micha and Stemmer, Uri},
  title =	{{How to Find a Point in the Convex Hull Privately}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.52},
  URN =		{urn:nbn:de:0030-drops-122107},
  doi =		{10.4230/LIPIcs.SoCG.2020.52},
  annote =	{Keywords: Differential privacy, Tukey depth, Convex hull}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.66
Incidences Between Points and Curves with Almost Two Degrees of Freedom

Authors: Micha Sharir and Oleg Zlydenko

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We study incidences between points and (constant-degree algebraic) curves in three dimensions, taken from a family C of curves that have almost two degrees of freedom, meaning that (i) every pair of curves of C intersect in O(1) points, (ii) for any pair of points p, q, there are only O(1) curves of C that pass through both points, and (iii) a pair p, q of points admit a curve of C that passes through both of them if and only if F(p,q)=0 for some polynomial F of constant degree associated with the problem. (As an example, the family of unit circles in ℝ³ that pass through some fixed point is such a family.) We begin by studying two specific instances of this scenario. The first instance deals with the case of unit circles in ℝ³ that pass through some fixed point (so called anchored unit circles). In the second case we consider tangencies between directed points and circles in the plane, where a directed point is a pair (p,u), where p is a point in the plane and u is a direction, and (p,u) is tangent to a circle γ if p ∈ γ and u is the direction of the tangent to γ at p. A lifting transformation due to Ellenberg et al. maps these tangencies to incidences between points and curves ("lifted circles") in three dimensions. In both instances we have a family of curves in ℝ³ with almost two degrees of freedom. We show that the number of incidences between m points and n anchored unit circles in ℝ³, as well as the number of tangencies between m directed points and n arbitrary circles in the plane, is O(m^(3/5)n^(3/5)+m+n) in both cases. We then derive a similar incidence bound, with a few additional terms, for more general families of curves in ℝ³ with almost two degrees of freedom, under a few additional natural assumptions. The proofs follow standard techniques, based on polynomial partitioning, but they face a critical novel issue involving the analysis of surfaces that are infinitely ruled by the respective family of curves, as well as of surfaces in a dual three-dimensional space that are infinitely ruled by the respective family of suitably defined dual curves. We either show that no such surfaces exist, or develop and adapt techniques for handling incidences on such surfaces. The general bound that we obtain is O(m^(3/5)n^(3/5)+m+n) plus additional terms that depend on how many curves or dual curves can lie on an infinitely-ruled surface.
Cite as

Micha Sharir and Oleg Zlydenko. Incidences Between Points and Curves with Almost Two Degrees of Freedom. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sharir_et_al:LIPIcs.SoCG.2020.66,
  author =	{Sharir, Micha and Zlydenko, Oleg},
  title =	{{Incidences Between Points and Curves with Almost Two Degrees of Freedom}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.66},
  URN =		{urn:nbn:de:0030-drops-122244},
  doi =		{10.4230/LIPIcs.SoCG.2020.66},
  annote =	{Keywords: Incidences, Polynomial partition, Degrees of freedom, Infinitely-ruled surfaces, Three dimensions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.64
Triangles and Girth in Disk Graphs and Transmission Graphs

Authors: Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Let S subset R^2 be a set of n sites, where each s in S has an associated radius r_s > 0. The disk graph D(S) is the undirected graph with vertex set S and an undirected edge between two sites s, t in S if and only if |st| <= r_s + r_t, i.e., if the disks with centers s and t and respective radii r_s and r_t intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph T(S) is the directed graph with vertex set S and a directed edge from a site s to a site t if and only if |st| <= r_s, i.e., if t lies in the disk with center s and radius r_s. We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in D(S) and in T(S). These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in D(S) and in T(S) can be found in O(n log n) expected time, and that the (weighted) girth of D(S) can be found in O(n log n) expected time. For this, we develop new tools for batched range searching that may be of independent interest.
Cite as

Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Triangles and Girth in Disk Graphs and Transmission Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.ESA.2019.64,
  author =	{Kaplan, Haim and Klost, Katharina and Mulzer, Wolfgang and Roditty, Liam and Seiferth, Paul and Sharir, Micha},
  title =	{{Triangles and Girth in Disk Graphs and Transmission Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{64:1--64:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.64},
  URN =		{urn:nbn:de:0030-drops-111859},
  doi =		{10.4230/LIPIcs.ESA.2019.64},
  annote =	{Keywords: disk graph, transmission graph, triangle, girth}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.8
General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem

Authors: Dror Aiger, Haim Kaplan, Efi Kokiopoulou, Micha Sharir, and Bernhard Zeisl

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We consider the classical camera pose estimation problem that arises in many computer vision applications, in which we are given n 2D-3D correspondences between points in the scene and points in the camera image (some of which are incorrect associations), and where we aim to determine the camera pose (the position and orientation of the camera in the scene) from this data. We demonstrate that this posing problem can be reduced to the problem of computing epsilon-approximate incidences between two-dimensional surfaces (derived from the input correspondences) and points (on a grid) in a four-dimensional pose space. Similar reductions can be applied to other camera pose problems, as well as to similar problems in related application areas. We describe and analyze three techniques for solving the resulting epsilon-approximate incidences problem in the context of our camera posing application. The first is a straightforward assignment of surfaces to the cells of a grid (of side-length epsilon) that they intersect. The second is a variant of a primal-dual technique, recently introduced by a subset of the authors [Aiger et al., 2017] for different (and simpler) applications. The third is a non-trivial generalization of a data structure Fonseca and Mount [Da Fonseca and Mount, 2010], originally designed for the case of hyperplanes. We present and analyze this technique in full generality, and then apply it to the camera posing problem at hand. We compare our methods experimentally on real and synthetic data. Our experiments show that for the typical values of n and epsilon, the primal-dual method is the fastest, also in practice.
Cite as

Dror Aiger, Haim Kaplan, Efi Kokiopoulou, Micha Sharir, and Bernhard Zeisl. General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aiger_et_al:LIPIcs.SoCG.2019.8,
  author =	{Aiger, Dror and Kaplan, Haim and Kokiopoulou, Efi and Sharir, Micha and Zeisl, Bernhard},
  title =	{{General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.8},
  URN =		{urn:nbn:de:0030-drops-104129},
  doi =		{10.4230/LIPIcs.SoCG.2019.8},
  annote =	{Keywords: Camera positioning, Approximate incidences, Incidences}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.62
On the Complexity of the k-Level in Arrangements of Pseudoplanes

Authors: Micha Sharir and Chen Ziv

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
A classical open problem in combinatorial geometry is to obtain tight asymptotic bounds on the maximum number of k-level vertices in an arrangement of n hyperplanes in R^d (vertices with exactly k of the hyperplanes passing below them). This is essentially a dual version of the k-set problem, which, in a primal setting, seeks bounds for the maximum number of k-sets determined by n points in R^d, where a k-set is a subset of size k that can be separated from its complement by a hyperplane. The k-set problem is still wide open even in the plane. In three dimensions, the best known upper and lower bounds are, respectively, O(nk^{3/2}) [M. Sharir et al., 2001] and nk * 2^{Omega(sqrt{log k})} [G. Tóth, 2000]. In its dual version, the problem can be generalized by replacing hyperplanes by other families of surfaces (or curves in the planes). Reasonably sharp bounds have been obtained for curves in the plane [M. Sharir and J. Zahl, 2017; H. Tamaki and T. Tokuyama, 2003], but the known upper bounds are rather weak for more general surfaces, already in three dimensions, except for the case of triangles [P. K. Agarwal et al., 1998]. The best known general bound, due to Chan [T. M. Chan, 2012] is O(n^{2.997}), for families of surfaces that satisfy certain (fairly weak) properties. In this paper we consider the case of pseudoplanes in R^3 (defined in detail in the introduction), and establish the upper bound O(nk^{5/3}) for the number of k-level vertices in an arrangement of n pseudoplanes. The bound is obtained by establishing suitable (and nontrivial) extensions of dual versions of classical tools that have been used in studying the primal k-set problem, such as the Lovász Lemma and the Crossing Lemma.
Cite as

Micha Sharir and Chen Ziv. On the Complexity of the k-Level in Arrangements of Pseudoplanes. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{sharir_et_al:LIPIcs.SoCG.2019.62,
  author =	{Sharir, Micha and Ziv, Chen},
  title =	{{On the Complexity of the k-Level in Arrangements of Pseudoplanes}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.62},
  URN =		{urn:nbn:de:0030-drops-104662},
  doi =		{10.4230/LIPIcs.SoCG.2019.62},
  annote =	{Keywords: k-level, pseudoplanes, arrangements, three dimensions, k-sets}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.26
Approximate Minimum-Weight Matching with Outliers Under Translation

Authors: Pankaj K. Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Micha Sharir, and Allen Xiao

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the L_p-norm of the tuple of the Euclidean distances between the pairs of matched points, for any p in [1,infty], and (b) for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region.
Cite as

Pankaj K. Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Micha Sharir, and Allen Xiao. Approximate Minimum-Weight Matching with Outliers Under Translation. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2018.26,
  author =	{Agarwal, Pankaj K. and Kaplan, Haim and Kipper, Geva and Mulzer, Wolfgang and Rote, G\"{u}nter and Sharir, Micha and Xiao, Allen},
  title =	{{Approximate Minimum-Weight Matching with Outliers Under Translation}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.26},
  URN =		{urn:nbn:de:0030-drops-99747},
  doi =		{10.4230/LIPIcs.ISAAC.2018.26},
  annote =	{Keywords: Minimum-weight partial matching, Pattern matching, Approximation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.50
Stabbing Pairwise Intersecting Disks by Five Points

Authors: Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, and Max Willert

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Suppose we are given a set D of n pairwise intersecting disks in the plane. A planar point set P stabs D if and only if each disk in D contains at least one point from P. We present a deterministic algorithm that takes O(n) time to find five points that stab D. Furthermore, we give a simple example of 13 pairwise intersecting disks that cannot be stabbed by three points. This provides a simple - albeit slightly weaker - algorithmic version of a classical result by Danzer that such a set D can always be stabbed by four points.
Cite as

Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, and Max Willert. Stabbing Pairwise Intersecting Disks by Five Points. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 50:1-50:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.ISAAC.2018.50,
  author =	{Har-Peled, Sariel and Kaplan, Haim and Mulzer, Wolfgang and Roditty, Liam and Seiferth, Paul and Sharir, Micha and Willert, Max},
  title =	{{Stabbing Pairwise Intersecting Disks by Five Points}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{50:1--50:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.50},
  URN =		{urn:nbn:de:0030-drops-99989},
  doi =		{10.4230/LIPIcs.ISAAC.2018.50},
  annote =	{Keywords: Disk graph, piercing set, LP-type problem}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.10
Union of Hypercubes and 3D Minkowski Sums with Random Sizes

Authors: Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Let T={triangle_1,...,triangle_n} be a set of of n pairwise-disjoint triangles in R^3, and let B be a convex polytope in R^3 with a constant number of faces. For each i, let C_i = triangle_i oplus r_i B denote the Minkowski sum of triangle_i with a copy of B scaled by r_i>0. We show that if the scaling factors r_1, ..., r_n are chosen randomly then the expected complexity of the union of C_1, ..., C_n is O(n^{2+epsilon), for any epsilon > 0; the constant of proportionality depends on epsilon and the complexity of B. The worst-case bound can be Theta(n^3). We also consider a special case of this problem in which T is a set of points in R^3 and B is a unit cube in R^3, i.e., each C_i is a cube of side-length 2r_i. We show that if the scaling factors are chosen randomly then the expected complexity of the union of the cubes is O(n log^2 n), and it improves to O(n log n) if the scaling factors are chosen randomly from a "well-behaved" probability density function (pdf). We also extend the latter results to higher dimensions. For any fixed odd value of d, we show that the expected complexity of the union of the hypercubes is O(n^floor[d/2] log n) and the bound improves to O(n^floor[d/2]) if the scaling factors are chosen from a "well-behaved" pdf. The worst-case bounds are Theta(n^2) in R^3, and Theta(n^{ceil[d/2]}) in higher dimensions.
Cite as

Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir. Union of Hypercubes and 3D Minkowski Sums with Random Sizes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ICALP.2018.10,
  author =	{Agarwal, Pankaj K. and Kaplan, Haim and Sharir, Micha},
  title =	{{Union of Hypercubes and 3D Minkowski Sums with Random Sizes}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.10},
  URN =		{urn:nbn:de:0030-drops-90147},
  doi =		{10.4230/LIPIcs.ICALP.2018.10},
  annote =	{Keywords: Computational geometry, Minkowski sums, Axis-parallel cubes, Union of geometric objects, Objects with random sizes}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.39
Dominance Product and High-Dimensional Closest Pair under L_infty

Authors: Omer Gold and Micha Sharir

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Given a set $S$ of $n$ points in \mathbb{R}^d, the Closest Pair problem is to find a pair of distinct points in S at minimum distance. When d is constant, there are efficient algorithms that solve this problem, and fast approximate solutions for general d. However, obtaining an exact solution in very high dimensions seems to be much less understood. We consider the high-dimensional L_\infty Closest Pair problem, where d=n^r for some r > 0, and the underlying metric is L_\infty. We improve and simplify previous results for L_\infty Closest Pair, showing that it can be solved by a deterministic strongly-polynomial algorithm that runs in O(DP(n,d)\log n) time, and by a randomized algorithm that runs in O(DP(n,d)) expected time, where DP(n,d) is the time bound for computing the dominance product for n points in \mathbb{R}^d. That is a matrix D, such that D[i,j] = \bigl| \{k \mid p_i[k] \leq p_j[k]\} \bigr|; this is the number of coordinates at which p_j dominates p_i. For integer coordinates from some interval [-M, M], we obtain an algorithm that runs in \tilde{O}\left(\min\{Mn^{\omega(1,r,1)},\, DP(n,d)\}\right) time, where \omega(1,r,1) is the exponent of multiplying an n \times n^r matrix by an n^r \times n matrix. We also give slightly better bounds for DP(n,d), by using more recent rectangular matrix multiplication bounds. Computing the dominance product itself is an important task, since it is applied in many algorithms as a major black-box ingredient, such as algorithms for APBP (all pairs bottleneck paths), and variants of APSP (all pairs shortest paths).
Cite as

Omer Gold and Micha Sharir. Dominance Product and High-Dimensional Closest Pair under L_infty. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 39:1-39:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gold_et_al:LIPIcs.ISAAC.2017.39,
  author =	{Gold, Omer and Sharir, Micha},
  title =	{{Dominance Product and High-Dimensional Closest Pair under L\underlineinfty}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{39:1--39:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.39},
  URN =		{urn:nbn:de:0030-drops-82268},
  doi =		{10.4230/LIPIcs.ISAAC.2017.39},
  annote =	{Keywords: Closest Pair, Dominance Product, L\underlineinfty Proximity, Rectangular Matrix Multiplication}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.4
Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats

Authors: Pankaj K. Agarwal, Natan Rubin, and Micha Sharir

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We consider the Approximate Nearest Neighbor (ANN) problem where the input set consists of n k-flats in the Euclidean Rd, for any fixed parameters k<d, and where, for each query point q, we want to return an input flat whose distance from q is at most (1 + epsilon) times the shortest such distance, where epsilon > 0 is another prespecified parameter. We present an algorithm that achieves this task with n^{k+1}(log(n)/epsilon)^O(1) storage and preprocessing (where the constant of proportionality in the big-O notation depends on d), and can answer a query in O(polylog(n)) time (where the power of the logarithm depends on d and k). In particular, we need only near-quadratic storage to answer ANN queries amidst a set of n lines in any fixed-dimensional Euclidean space. As a by-product, our approach also yields an algorithm, with similar performance bounds, for answering exact nearest neighbor queries amidst k-flats with respect to any polyhedral distance function. Our results are more general, in that they also provide a tradeoff between storage and query time.
Cite as

Pankaj K. Agarwal, Natan Rubin, and Micha Sharir. Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ESA.2017.4,
  author =	{Agarwal, Pankaj K. and Rubin, Natan and Sharir, Micha},
  title =	{{Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.4},
  URN =		{urn:nbn:de:0030-drops-78182},
  doi =		{10.4230/LIPIcs.ESA.2017.4},
  annote =	{Keywords: Approximate nearest neighbor search, k-flats, Polyhedral distance functions, Linear programming queries}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.5
Output Sensitive Algorithms for Approximate Incidences and Their Applications

Authors: Dror Aiger, Haim Kaplan, and Micha Sharir

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
An epsilon-approximate incidence between a point and some geometric object (line, circle, plane, sphere) occurs when the point and the object lie at distance at most epsilon from each other. Given a set of points and a set of objects, computing the approximate incidences between them is a major step in many database and web-based applications in computer vision and graphics, including robust model fitting, approximate point pattern matching, and estimating the fundamental matrix in epipolar (stereo) geometry. In a typical approximate incidence problem of this sort, we are given a set P of m points in two or three dimensions, a set S of n objects (lines, circles, planes, spheres), and an error parameter epsilon>0, and our goal is to report all pairs (p,s) in P times S that lie at distance at most epsilon from one another. We present efficient output-sensitive approximation algorithms for quite a few cases, including points and lines or circles in the plane, and points and planes, spheres, lines, or circles in three dimensions. Several of these cases arise in the applications mentioned above. Our algorithms report all pairs at distance <= epsilon, but may also report additional pairs, all of which are guaranteed to be at distance at most alphaepsilon, for some constant alpha>1. Our algorithms are based on simple primal and dual grid decompositions and are easy to implement. We note though that (a) the use of duality, which leads to significant improvements in the overhead cost of the algorithms, appears to be novel for this kind of problems; (b) the correct choice of duality in some of these problems is fairly intricate and requires some care; and (c) the correctness and performance analysis of the algorithms (especially in the more advanced versions) is fairly non-trivial. We analyze our algorithms and prove guaranteed upper bounds on their running time and on the "distortion" parameter alpha. We also briefly describe the motivating applications, and show how they can effectively exploit our solutions. The superior theoretical bounds on the performance of our algorithms, and their simplicity, make them indeed ideal tools for these applications. In a series of preliminary experimentations (not included in this abstract), we substantiate this feeling, and show that our algorithms lead in practice to significant improved performance of the aforementioned applications.
Cite as

Dror Aiger, Haim Kaplan, and Micha Sharir. Output Sensitive Algorithms for Approximate Incidences and Their Applications. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aiger_et_al:LIPIcs.ESA.2017.5,
  author =	{Aiger, Dror and Kaplan, Haim and Sharir, Micha},
  title =	{{Output Sensitive Algorithms for Approximate Incidences and Their Applications}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.5},
  URN =		{urn:nbn:de:0030-drops-78224},
  doi =		{10.4230/LIPIcs.ESA.2017.5},
  annote =	{Keywords: Approximate incidences, near-neighbor reporting, duality, grid-based approximation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.42
Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy

Authors: Omer Gold and Micha Sharir

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Given a set of n real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Gronlund and Pettie [FOCS'14], a simple Theta(n^2)-time deterministic algorithm for this problem was conjectured to be optimal. Over the years many algorithmic problems have been shown to be reducible from the 3SUM problem or its variants, including the more generalized forms of the problem, such as k-SUM and k-variate linear degeneracy testing (k-LDT). The conjectured hardness of these problems have become extremely popular for basing conditional lower bounds for numerous algorithmic problems in P. In this paper, we show that the randomized 4-linear decision tree complexity of 3SUM is O(n^{3/2}), and that the randomized (2k-2)-linear decision tree complexity of k-SUM and k-LDT is O(n^{k/2}), for any odd >= 3. These bounds improve (albeit randomized) the corresponding O(n^{3/2} sqrt{log n}) and O(n^{k/2} sqrt{log n}) decision tree bounds obtained by Gr{\o}nlund and Pettie. Our technique includes a specialized randomized variant of fractional cascading data structure. Additionally, we give another deterministic algorithm for 3SUM that runs in O(n^2 log log n / log n ) time. The latter bound matches a recent independent bound by Freund [Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use of the word-RAM model.
Cite as

Omer Gold and Micha Sharir. Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gold_et_al:LIPIcs.ESA.2017.42,
  author =	{Gold, Omer and Sharir, Micha},
  title =	{{Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.42},
  URN =		{urn:nbn:de:0030-drops-78364},
  doi =		{10.4230/LIPIcs.ESA.2017.42},
  annote =	{Keywords: 3SUM, k-SUM, Linear Degeneracy, Linear Decision Trees, Fractional Cascading}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.52
Finding Axis-Parallel Rectangles of Fixed Perimeter or Area Containing the Largest Number of Points

Authors: Haim Kaplan, Sasanka Roy, and Micha Sharir

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Let P be a set of n points in the plane in general position, and consider the problem of finding an axis-parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P. We present an exact algorithm that finds such a rectangle in O(n^{5/2} log n) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O(nk^{3/2} log k) time, and (ii) an approximation algorithm that finds, in O(n+(n/(k epsilon^5))*log^{5/2}(n/k)log((1/epsilon) log(n/k))) time, a rectangle of the given perimeter or diagonal that contains at least (1-epsilon)k points of P, where k is the optimum value. We then show how to turn this algorithm into one that finds, for a given k, an axis-parallel rectangle of smallest perimeter (or area, or diagonal) that contains k points of P. We obtain the first subcubic algorithms for these problems, significantly improving the current state of the art.
Cite as

Haim Kaplan, Sasanka Roy, and Micha Sharir. Finding Axis-Parallel Rectangles of Fixed Perimeter or Area Containing the Largest Number of Points. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 52:1-52:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.ESA.2017.52,
  author =	{Kaplan, Haim and Roy, Sasanka and Sharir, Micha},
  title =	{{Finding Axis-Parallel Rectangles of Fixed Perimeter or Area Containing the Largest Number of Points}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{52:1--52:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.52},
  URN =		{urn:nbn:de:0030-drops-78608},
  doi =		{10.4230/LIPIcs.ESA.2017.52},
  annote =	{Keywords: Computational geometry, geometric optimization, rectangles, perimeter, area}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.25
Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

Authors: Omer Gold and Micha Sharir

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology, consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points in X = R^d are long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional case d = 1, which is perhaps one of the most used in practice. In this paper, we break the nearly 50 years old quadratic time bound for computing DTW or GED between two sequences of n points in R, by presenting deterministic algorithms that run in O( n^2 log log log n / log log n ) time. Our algorithms can be extended to work also for higher dimensional spaces R^d, for any constant d, when the underlying distance-metric dist is polyhedral (e.g., L_1, L_infty).
Cite as

Omer Gold and Micha Sharir. Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gold_et_al:LIPIcs.ICALP.2017.25,
  author =	{Gold, Omer and Sharir, Micha},
  title =	{{Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.25},
  URN =		{urn:nbn:de:0030-drops-73820},
  doi =		{10.4230/LIPIcs.ICALP.2017.25},
  annote =	{Keywords: Dynamic Time Warping, Geometric Edit Distance, Time Series, Points Matching, Geometric Matching}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SoCG.2017.2
The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art (Invited Talk)

Authors: Micha Sharir

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
For the past 10 years, combinatorial geometry (and to some extent, computational geometry too) has gone through a dramatic revolution, due to the infusion of techniques from algebraic geometry and algebra that have proven effective in solving a variety of hard problems that were thought to be unreachable with more traditional techniques. The new era has begun with two groundbreaking papers of Guth and Katz, the second of which has (almost completely) solved the distinct distances problem of Erdos, open since 1946. In this talk I will survey some of the progress that has been made since then, including a variety of problems on distinct and repeated distances and other configurations, on incidences between points and lines, curves, and surfaces in two, three, and higher dimensions, on polynomials vanishing on Cartesian products with applications, on cycle elimination for lines and triangles in three dimensions, on range searching with semialgebraic sets, and I will most certainly run out of time while doing so.
Cite as

Micha Sharir. The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art (Invited Talk). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{sharir:LIPIcs.SoCG.2017.2,
  author =	{Sharir, Micha},
  title =	{{The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.2},
  URN =		{urn:nbn:de:0030-drops-72384},
  doi =		{10.4230/LIPIcs.SoCG.2017.2},
  annote =	{Keywords: Combinatorial Geometry, Incidences, Polynomial method, Algebraic Geometry, Distances}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.41
A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM

Authors: Esther Ezra and Micha Sharir

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
We show that the k-SUM problem can be solved by a linear decision tree of depth O(n^2 log^2 n),improving the recent bound O(n^3 log^3 n) of Cardinal et al. Our bound depends linearly on k, and allows us to conclude that the number of linear queries required to decide the n-dimensional Knapsack or SubsetSum problems is only O(n^3 log n), improving the currently best known bounds by a factor of n. Our algorithm extends to the RAM model, showing that the k-SUM problem can be solved in expected polynomial time, for any fixed k, with the above bound on the number of linear queries. Our approach relies on a new point-location mechanism, exploiting "Epsilon-cuttings" that are based on vertical decompositions in hyperplane arrangements in high dimensions. A major side result of the analysis in this paper is a sharper bound on the complexity of the vertical decomposition of such an arrangement (in terms of its dependence on the dimension). We hope that this study will reveal further structural properties of vertical decompositions in hyperplane arrangements.
Cite as

Esther Ezra and Micha Sharir. A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ezra_et_al:LIPIcs.SoCG.2017.41,
  author =	{Ezra, Esther and Sharir, Micha},
  title =	{{A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{41:1--41:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.41},
  URN =		{urn:nbn:de:0030-drops-71853},
  doi =		{10.4230/LIPIcs.SoCG.2017.41},
  annote =	{Keywords: k-SUM and k-LDT, linear decision tree, hyperplane arrangements, point-location, vertical decompositions, Epsilon-cuttings}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.522
Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited

Authors: Orit E. Raz, Micha Sharir, and Frank de Zeeuw

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Let F in Complex[x,y,z] be a constant-degree polynomial, and let A,B,C be sets of complex numbers with |A|=|B|=|C|=n. We show that F vanishes on at most O(n^{11/6}) points of the Cartesian product A x B x C (where the constant of proportionality depends polynomially on the degree of F), unless F has a special group-related form. This improves a theorem of Elekes and Szabo [ES12], and generalizes a result of Raz, Sharir, and Solymosi [RSS14a]. The same statement holds over R. When A, B, C have different sizes, a similar statement holds, with a more involved bound replacing O(n^{11/6}). This result provides a unified tool for improving bounds in various Erdos-type problems in combinatorial geometry, and we discuss several applications of this kind.
Cite as

Orit E. Raz, Micha Sharir, and Frank de Zeeuw. Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 522-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SOCG.2015.522,
  author =	{Raz, Orit E. and Sharir, Micha and de Zeeuw, Frank},
  title =	{{Polynomials Vanishing on Cartesian Products: The Elekes-Szab\'{o} Theorem Revisited}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{522--536},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.522},
  URN =		{urn:nbn:de:0030-drops-51031},
  doi =		{10.4230/LIPIcs.SOCG.2015.522},
  annote =	{Keywords: Combinatorial geometry, incidences, polynomials}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.553
Incidences between Points and Lines in Three Dimensions

Authors: Micha Sharir and Noam Solomon

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We give a fairly elementary and simple proof that shows that the number of incidences between m points and n lines in R^3, so that no plane contains more than s lines, is O(m^{1/2}n^{3/4} + m^{2/3}n^{1/3}s^{1/3} + m + n) (in the precise statement, the constant of proportionality of the first and third terms depends, in a rather weak manner, on the relation between m and n). This bound, originally obtained by Guth and Katz as a major step in their solution of Erdos's distinct distances problem, is also a major new result in incidence geometry, an area that has picked up considerable momentum in the past six years. Its original proof uses fairly involved machinery from algebraic and differential geometry, so it is highly desirable to simplify the proof, in the interest of better understanding the geometric structure of the problem, and providing new tools for tackling similar problems. This has recently been undertaken by Guth. The present paper presents a different and simpler derivation, with better bounds than those in Guth, and without the restrictive assumptions made there. Our result has a potential for applications to other incidence problems in higher dimensions.
Cite as

Micha Sharir and Noam Solomon. Incidences between Points and Lines in Three Dimensions. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 553-568, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{sharir_et_al:LIPIcs.SOCG.2015.553,
  author =	{Sharir, Micha and Solomon, Noam},
  title =	{{Incidences between Points and Lines in Three Dimensions}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{553--568},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.553},
  URN =		{urn:nbn:de:0030-drops-51107},
  doi =		{10.4230/LIPIcs.SOCG.2015.553},
  annote =	{Keywords: Combinatorial Geometry, Algebraic Geometry, Incidences, The Polynomial Method}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.569
The Number of Unit-Area Triangles in the Plane: Theme and Variations

Authors: Orit E. Raz and Micha Sharir

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We show that the number of unit-area triangles determined by a set S of n points in the plane is O(n^{20/9}), improving the earlier bound O(n^{9/4}) of Apfelbaum and Sharir. We also consider two special cases of this problem: (i) We show, using a somewhat subtle construction, that if S consists of points on three lines, the number of unit-area triangles that S spans can be Omega(n^2), for any triple of lines (it is always O(n^2) in this case). (ii) We show that if S is a convex grid of the form A x B, where A, B are convex sets of n^{1/2} real numbers each (i.e., the sequences of differences of consecutive elements of A and of B are both strictly increasing), then S determines O(n^{31/14}) unit-area triangles.
Cite as

Orit E. Raz and Micha Sharir. The Number of Unit-Area Triangles in the Plane: Theme and Variations. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 569-583, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SOCG.2015.569,
  author =	{Raz, Orit E. and Sharir, Micha},
  title =	{{The Number of Unit-Area Triangles in the Plane: Theme and Variations}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{569--583},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.569},
  URN =		{urn:nbn:de:0030-drops-51125},
  doi =		{10.4230/LIPIcs.SOCG.2015.569},
  annote =	{Keywords: Combinatorial geometry, incidences, repeated configurations}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact